#include<iostream>
#include<vector>

using namespace std;

class Solution 
{
    string num[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    void combine(string digit, int level, string combinestr, vector<string>& v)
    {
        if (level == digit.size())
        {
            v.push_back(combinestr);
            return;
        }
        size_t number = (digit[level] - '0');
        for (size_t i = 0; i < num[number].size(); i++)
        {
            combine(digit, level + 1, combinestr + num[number][i], v);
        }
    }
    vector<string>v;
    vector<string> letterCombinations(string digits) 
    {
        if (digits == "")return v;
        combine(digits, 0, "", v);
        return v;
    }
};


class Solution2 {
public:
    string str[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    string path;
    vector<string>ret;
    void dfs(string digits, int pos)
    {
        if (pos == digits.size())
        {
            ret.push_back(path);
            return;
        }
        string combine = str[digits[pos] - '0'];
        for (int i = 0; i < combine.size(); i++)
        {
            path.push_back(combine[i]);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        dfs(digits, 0);
        return ret;
    }
};